1. Technical Field
The invention relates to a device for computing the digital transform of a signal which may be implemented on silicon.
There is a need for real time computation of transforms of a signal in a number of technical fields. Fast computation devices exist which fulfill that need when the transforms are of small length. On the other hand, such devices are not appropriate for computing transforms of great length, since the amount of computation which is required when conventional approaches are used is such that they cannot be carried out in real time.
As an example, there is a need for implementing a length 128 Fourier transform on PCM signals whose samples are available as eight bit words for videotext. It would also be of advantage to compute discrete cosine transforms (DCTs) of length 8 or 16 for image processing.
2. Prior Art
Many fast DCT algorithms have been proposed. Examples may be found in CHEN et al "A fast computational Algorithm for the Discrete Cosine Transform" in IEEE Trans. on comm., Vol. COM-25 No. 9, September 1977, pages 1004-1011; in JALALI et al "A High-speed FDCT Processor for real-time Processing of NTSC color TV signal" in IEEE Trans. on elec. comp., vol. EMC. 24, No. 2, May 1982, pages 278-286; and in LEE "A new algorithm to compute the Discrete Cosine Transform", IEEE Trans. on ASSP., Vol. ASSP-32, No. 6, December 1984, pages 1243-1245.
None of the algorithms simultaneously provide minimum arithmetic complexity, full regularity of the graph, good noise performances and high speed.